package algorithmExample.Heap;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/14 9:34
 */
public class MergeKSortedLists2 {
    //分治算法
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        int right = lists.length - 1, left = 0;
        while (right > 0) {
            while (left < right) {
                lists[left] = mergeTwoListNode(lists[left], lists[right]);
                right--;
                left++;
            }
            left = 0;
        }
        return lists[0];
    }

    private ListNode mergeTwoListNode(ListNode left, ListNode right) {
        ListNode start = new ListNode(0);
        ListNode result = start;
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        while (left != null || right != null) {
            if (left != null && (right == null || left.val <= right.val)) {
                start.next = left;
                start = start.next;
                left = left.next;
            } else {
                start.next = right;
                start = start.next;
                right = right.next;
            }
        }

        return result.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(4);
        listNode1.next.next = new ListNode(5);

        ListNode listNode2 = new ListNode(1);
        listNode2.next = new ListNode(3);
        listNode2.next.next = new ListNode(4);

//        ListNode listNode2 = null;
        ListNode listNode3 = new ListNode(2);
        listNode3.next = new ListNode(6);

        ListNode result = new MergeKSortedLists2().mergeKLists(new ListNode[]{listNode1, listNode2, listNode3});
        System.out.println("result:" + result);
    }
}
